package com.zl.test;

import javax.crypto.Cipher;
import java.awt.font.NumericShaper;
import java.util.*;

/**
 * @author zengle
 * @create 2021-07-06 19:18
 */
public class Question {

    public static class Position {

        int row;
        int cow;

        public Position(int row, int cow) {
            this.row = row;
            this.cow = cow;
        }

        @Override
        public String toString() {
            return "( " + row + " , " + cow + " )";
        }
    }

    /**
     * @Description： 获得一条走出迷宫的路径 @Params: int[] nums 迷宫的布置图
     * @return: List ret 保存有结果的list
     * @author: Mr.Wang
     * @create: 9:50
     */
    public static class MyStack {

        int len;
        Position[] position;
        int size;

        public MyStack(int len) {
            this.len = len;
            position = new Position[len];
        }

        public MyStack() {
        }

        public void add(Position value) {
            if (size >= len) {
                throw new RuntimeException("栈已满");
            }
            position[++size] = value;  //1
        }

        public Position pop() {

            if (!isEmpty()) {

                return position[size--];  //1

            } else {
                throw new RuntimeException("栈已空");
            }
        }

        public Position peek() {
            return position[size];
        }

        public boolean isEmpty() {

            return size >= 1 ? false : true;
        }
    }

    /**
     * @param nums 迷宫
     * @param m    起始 行
     * @param n    起始 列
     * @return
     */
    public static List<int[]> solutionDFS(int[][] nums, int m, int n) {
        int rows = nums.length;
        int cows = nums[0].length;
        int[][] visited = new int[rows][cows];
        Stack<Position> stack = new Stack<>();
        Position p = new Position(m, n);
        stack.add(p);
        visited[m][n] = 1;
        Position temp;
        while (!stack.isEmpty() && !(p.row == rows - 1 && p.cow == cows - 1)) {
            p = stack.peek();
            if (p.cow + 1 < cows && nums[p.row][p.cow + 1] == 0 && visited[p.row][p.cow + 1] != 1) { // 右

                temp = new Position(p.row, p.cow + 1);
                stack.add(temp);
                visited[temp.row][temp.cow] = 1;
            } else if (p.row + 1 < rows
                    && nums[p.row + 1][p.cow] == 0
                    && visited[p.row + 1][p.cow] != 1) { // 下
                temp = new Position(p.row + 1, p.cow);
                stack.add(temp);
                visited[temp.row][temp.cow] = 1;
            } else if (p.cow - 1 > -1
                    && nums[p.row][p.cow - 1] == 0
                    && visited[p.row][p.cow - 1] != 1) { // 左
                temp = new Position(p.row, p.cow - 1);
                stack.add(temp);
                visited[temp.row][temp.cow] = 1;
            } else if (p.row - 1 > -1
                    && nums[p.row - 1][p.cow] == 0
                    && visited[p.row - 1][p.cow] != 1) { // 上
                temp = new Position(p.row - 1, p.cow);
                stack.add(temp);
                visited[temp.row][temp.cow] = 1;
            } else { // 不通
                stack.pop();
            }
            //当来到了最右 最下
            if (p.cow == cows - 1 || p.row == rows - 1) {
                stack.add(new Position(p.row, p.cow));
                break;
            }
        }
        if (stack.isEmpty()) return new LinkedList<>();
        Deque<int[]> deque = new LinkedList<>();
        for (Position po : stack) {
            deque.addLast(new int[]{po.row, po.cow});
        }
        return (List) deque;
    }


    public static List<int[]> solutionsDFS2(int[][] nums, int m, int n) {
        int rows = nums.length;
        int cols = nums[0].length;
        MyStack myStack = new MyStack(100);

        Position p = new Position(m, n);
        int[][] visted = new int[rows][cols];
        Position temp;
        visted[m][n] = 1;
        myStack.add(p);
        while (!myStack.isEmpty()) {
            Position po = myStack.peek();

            //当来到了最右 最下
            if (po.cow == cols - 1 || po.row == rows - 1) {
                myStack.add(new Position(po.row, po.cow));
                break;
            }

            if (po.cow + 1 < cols && nums[po.row][po.cow + 1] == 0 && visted[po.row][po.cow + 1] != 1) {  //右
                temp = new Position(po.row, po.cow + 1);
                myStack.add(temp);
                visted[temp.row][temp.cow] = 1;
            } else if (po.row + 1 < rows && nums[po.row + 1][po.cow] == 0 && visted[po.row + 1][po.cow] != 1) {  //下
                temp = new Position(po.row + 1, po.cow);
                myStack.add(temp);
                visted[temp.row][temp.cow] = 1;
            } else if (po.cow - 1 > -1 && nums[po.row][po.cow - 1] == 0 && visted[po.row][po.cow - 1] != 1) { //左
                temp = new Position(po.row, po.cow - 1);
                myStack.add(temp);
                visted[temp.row][temp.cow] = 1;
            } else if (po.row - 1 > -1 && nums[po.row - 1][po.cow] == 0 && visted[po.row - 1][po.cow] != 1) { // 上
                temp = new Position(po.row - 1, po.cow);
                myStack.add(temp);
                visted[temp.row][temp.cow] = 1;
            } else {  // 不通
                myStack.pop();
            }


        }


        List<int[]> list = new LinkedList<>();
        while (!myStack.isEmpty()) {
            Position position = myStack.pop();
            ((LinkedList<int[]>) list).addFirst(new int[]{position.row, position.cow});
        }


        return list;
    }

    /**
     * @Description： 获得走出迷宫的最小步数 @Params: int[] nums 迷宫的布置图
     * @return: int ret 走出迷宫需要的最小步骤
     * @author: Mr.Wang
     * @create: 10:28
     */
    public static int solutionBFS(int[][] nums) {
        int rows = nums.length;
        int cows = nums[0].length;
        int[][] count = new int[rows][cows];
        for (int i = 0; i < rows; i++) {
            Arrays.fill(count[i], Integer.MAX_VALUE);
        }
        count[0][0] = 0;
        Deque<Position> deque = new LinkedList<>(); // 栈
        Position p = new Position(0, 0);
        deque.add(p);
        int[] r = {0, 1, 0, -1};
        int[] c = {1, 0, -1, 0};
        while (!deque.isEmpty()) {
            p = deque.pollLast(); // 尾出
            for (int i = 0; i < 4; i++) {
                int tempR = p.row + r[i];
                int tempC = p.cow + c[i];
                if (tempR > -1 && tempR < rows && tempC > -1 && tempC < cows && nums[tempR][tempC] == 0) {
                    if (count[tempR][tempC] > count[p.row][p.cow] + 1) {
                        count[tempR][tempC] = count[p.row][p.cow] + 1;
                        Position temp = new Position(tempR, tempC);
                        deque.addFirst(temp); // 头入
                    }
                }
            }
        }
        return count[rows - 1][cows - 1];
    }

    public static void main(String[] args) {
        int[][] nums = {
                {0, 0, 1, 0, 0, 0, 1, 0},
                {0, 0, 1, 0, 0, 0, 1, 0},
                {0, 0, 1, 0, 1, 1, 0, 1},
                {0, 1, 1, 1, 0, 0, 1, 0},
                {0, 0, 0, 1, 0, 0, 0, 0},
                {0, 1, 0, 0, 0, 1, 0, 1},
                {0, 1, 1, 1, 1, 0, 0, 1},
                {1, 1, 0, 0, 0, 1, 0, 1},
                {1, 1, 0, 0, 0, 0, 0, 0}
        };

        // 1001
        // 1100
        // 1111
        int[][] num = {
                {1, 0, 1, 1},
                {1, 0, 0, 1},
                {1, 1, 0, 0},
                {1, 1, 1, 1}
        };
        List<int[]> ret = Question.solutionDFS(nums, 0, 0);
        for (int[] r : ret) {
            System.out.println(r[0] + " " + r[1]);
        }
//    int retBFS = Question.solutionBFS(num);
//    System.out.println(retBFS);
    }
}
